class TreeNode {
    int val; // 节点的值
    TreeNode left; // 左子节点
    TreeNode right; // 右子节点

    TreeNode() {} // 默认构造函数
    TreeNode(int val) { this.val = val; } // 带值的构造函数
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    int res, k;

    // 中序遍历函数
    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left); // 遍历左子树
        if (k == 0) return; // 如果已经找到第 k 小的元素，直接返回
        if (--k == 0) res = root.val; // 如果当前节点是第 k 小的节点，记录结果
        dfs(root.right); // 遍历右子树
    }

    // 查找第 k 小的元素
    public int kthSmallest(TreeNode root, int k) {
        this.k = k; // 初始化 k
        dfs(root); // 调用中序遍历
        return res; // 返回结果
    }

    public static void main(String[] args) {
        //       5
        //      / \
        //     3   6
        //    / \
        //   2   4
        //  /
        // 1
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3, new TreeNode(2, new TreeNode(1), null), new TreeNode(4));
        root.right = new TreeNode(6);

        Solution solution = new Solution();

        // 查找第 k 小的元素
        int k = 3;
        int result = solution.kthSmallest(root, k);

        System.out.println("The " + k + "rd smallest element is: " + result);
    }
}